/**
 * 数组a，存储无需的ki，i从1到n
 * 要求将kn排序放到正确的位置上，要求比较次数不超过n
 * 使用快速排序的思想，只是将kn作为中枢元素
 * 不可用使用插入排序，插入排序要先将前面的元素排序好，之后才是n的复杂度
 */

int partition(int k[], int n)
{
    int i = 1;
    int j = n;
    int pivot = k[j]; // Kn作为中枢元素
    while (i < j)
    {
        //两个while寻找的时候，都会略过和中枢相同的数字
        while (i < j && k[i] <= pivot)//从左往右找比中枢大的
        {
            i++;
        }
        if (i < j)
        {
            k[j] = k[i];
        }
        while (i < j && k[j] >= pivot)//从右往左找比中枢小的
        {
            j--;
        }
        if (i < j)//交换左右两个元素
        {
            k[i] = k[j];
        }
    }
    k[i] = pivot;
    return i;
}
